//70. 爬楼梯

//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

//class Solution {
//public:
//    int climbStairs(int n) {
//        vector<int> f(n + 1);
//        f[0] = f[1] = 1;
//        for (int i = 2; i <= n; i++) {
//            f[i] = f[i - 1] + f[i - 2];
//        }
//        return f[n];
//    }
//};

//746. 使用最小花费爬楼梯

//给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
//你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
//请你计算并返回达到楼梯顶部的最低花费。

//class Solution {
//public:
//    int minCostClimbingStairs(vector<int>& cost) {
//        int n = cost.size();
//        vector<int> f(n + 1);
//        for (int i = 2; i <= n; i++) {
//            f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
//        }
//        return f[n];
//    }
//};

//3693. 爬楼梯 II

//你正在爬一个有 n + 1 级台阶的楼梯，台阶编号从 0 到 n。
//你还得到了一个长度为 n 的 下标从 1 开始 的整数数组 costs，其中 costs[i] 是第 i 级台阶的成本。
//从第 i 级台阶，你 只能 跳到第 i + 1、i + 2 或 i + 3 级台阶。从第 i 级台阶跳到第 j 级台阶的成本定义为： costs[j] + (j - i)2
//你从第 0 级台阶开始，初始 cost = 0。
//返回到达第 n 级台阶所需的 最小 总成本。

//class Solution {
//public:
//    int climbStairs(int n, vector<int>& costs) {
//        vector<int> memo(n + 1);
//
//        auto dfs = [&](this auto&& dfs, int i) -> int {
//            if (i == 0) {
//                return 0;
//            }
//            int& res = memo[i];
//            if (res) {
//                return res;
//            }
//            res = INT_MAX;
//            for (int j = max(i - 3, 0); j < i; j++) {
//                res = min(res, dfs(j) + (i - j) * (i - j));
//            }
//            res += costs[i - 1];
//            return res;
//            };
//
//        return dfs(n);
//    }
//};

//377. 组合总和 Ⅳ

//给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
//题目数据保证答案符合 32 位整数范围。

//class Solution {
//public:
//    int combinationSum4(vector<int>& nums, int target) {
//        ranges::sort(nums);
//        vector<unsigned> f(target + 1);
//        f[0] = 1;
//        for (int i = 1; i <= target; i++) {
//            for (int x : nums) {
//                if (x > i) {
//                    break;
//                }
//                f[i] += f[i - x];
//            }
//        }
//        return f[target];
//    }
//};

//2466. 统计构造好字符串的方案数

//给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：
//将 '0' 在字符串末尾添加 zero  次。
//将 '1' 在字符串末尾添加 one 次。
//以上操作可以执行任意次。
//如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。
//请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

//class Solution {
//public:
//    int countGoodStrings(int low, int high, int zero, int one) {
//        const int MOD = 1'000'000'007;
//        int ans = 0;
//        vector<int> f(high + 1);
//        f[0] = 1;
//        for (int i = 1; i <= high; i++) {
//            if (i >= zero) f[i] = f[i - zero];
//            if (i >= one)  f[i] = (f[i] + f[i - one]) % MOD;
//            if (i >= low)  ans = (ans + f[i]) % MOD;
//        }
//        return ans;
//    }
//};

//2266. 统计打字方案数

//Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。
//为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。
//比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母  'k' 。
//注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。
//但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。
//比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。
//给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。
//由于答案可能很大，将它对 109 + 7 取余 后返回。

//const int MOD = 1'000'000'007;
//const int MX = 100'001;
//
//long long f[MX], g[MX];
//
//int init = []() {
//    f[0] = g[0] = 1;
//    f[1] = g[1] = 1;
//    f[2] = g[2] = 2;
//    f[3] = g[3] = 4;
//    for (int i = 4; i < MX; ++i) {
//        f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % MOD;
//        g[i] = (g[i - 1] + g[i - 2] + g[i - 3] + g[i - 4]) % MOD;
//    }
//    return 0;
//    }();
//
//class Solution {
//public:
//    int countTexts(string s) {
//        long long ans = 1;
//        int cnt = 0, n = s.size();
//        for (int i = 0; i < n; i++) {
//            char c = s[i];
//            cnt++;
//            if (i == n - 1 || c != s[i + 1]) {
//                ans = ans * (c != '7' && c != '9' ? f[cnt] : g[cnt]) % MOD;
//                cnt = 0;
//            }
//        }
//        return ans;
//    }
//};

//198. 打家劫舍

//你是一个专业的小偷，计划偷窃沿街的房屋。
//每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
//给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n + 2);
//        for (int i = 0; i < n; i++) {
//            f[i + 2] = max(f[i + 1], f[i] + nums[i]);
//        }
//        return f[n + 1];
//    }
//};

//213. 打家劫舍 II

//你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
//同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
//给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

//class Solution {
//    // 198. 打家劫舍
//    int rob1(vector<int>& nums, int start, int end) {
//        int f0 = 0, f1 = 0;
//        for (int i = start; i < end; i++) {
//            int new_f = max(f1, f0 + nums[i]);
//            f0 = f1;
//            f1 = new_f;
//        }
//        return f1;
//    }
//
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        return max(nums[0] + rob1(nums, 2, n - 1), rob1(nums, 1, n));
//    }
//};

//2320. 统计放置房子的方式数

//一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
//现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
//注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

//const int MOD = 1'000'000'007;
//const int MX = 10'001;
//
//int f[MX] = { 1, 2 };
//
//int init = []() {
//    for (int i = 2; i < MX; i++) {
//        f[i] = (f[i - 1] + f[i - 2]) % MOD;
//    }
//    return 0;
//    }();
//
//class Solution {
//public:
//    int countHousePlacements(int n) {
//        return 1LL * f[n] * f[n] % MOD;
//    }
//};

//740. 删除并获得点数

//给你一个整数数组 nums ，你可以对它进行一些操作。
//每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
//开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

//class Solution {
//    // 198. 打家劫舍
//    int rob(vector<int>& nums) {
//        int f0 = 0, f1 = 0;
//        for (int x : nums) {
//            int new_f = max(f1, f0 + x);
//            f0 = f1;
//            f1 = new_f;
//        }
//        return f1;
//    }
//
//public:
//    int deleteAndEarn(vector<int>& nums) {
//        int mx = ranges::max(nums);
//        vector<int> a(mx + 1);
//        for (int x : nums) {
//            a[x] += x; // 统计等于 x 的元素之和
//        }
//        return rob(a);
//    }
//};

//3186. 施咒的最大总伤害

//一个魔法师有许多不同的咒语。
//给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
//已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
//每个咒语最多只能被使用 一次 。
//请你返回这个魔法师可以达到的伤害值之和的 最大值 。

//class Solution {
//public:
//    long long maximumTotalDamage(vector<int>& power) {
//        unordered_map<int, long long> cnt;
//        for (int x : power) {
//            cnt[x] += x;
//        }
//
//        vector<pair<int, long long>> a(cnt.begin(), cnt.end());
//        ranges::sort(a);
//
//        int n = a.size();
//        vector<long long> f(n + 1);
//        for (int i = 0, j = 0; i < n; i++) {
//            auto& [x, c] = a[i];
//            while (a[j].first < x - 2) {
//                j++;
//            }
//            f[i + 1] = max(f[i], f[j] + c);
//        }
//        return f[n];
//    }
//};

//2140. 解决智力问题

//给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。
//这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。
//解决问题 i 将让你 获得  pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。
//如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
//比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
//如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
//如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。
//请你返回这场考试里你能获得的 最高 分数。

//class Solution {
//public:
//    long long mostPoints(vector<vector<int>>& questions) {
//        int n = questions.size();
//        vector<long long> f(n + 1);
//        for (int i = n - 1; i >= 0; i--) {
//            int j = min(i + questions[i][1] + 1, n);
//            f[i] = max(f[i + 1], f[j] + questions[i][0]);
//        }
//        return f[0];
//    }
//};

//2606. 找到最大开销的子字符串

//给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。
//子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。
//字符的价值 定义如下：
//如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
//比方说，'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。
//否则，如果这个字符在 chars 中的位置为 i ，那么它的价值就是 vals[i] 。
//请你返回字符串 s 的所有子字符串中的最大开销。

//class Solution {
//public:
//    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
//        int mapping[26]{};
//        iota(mapping, mapping + 26, 1);
//        for (int i = 0, n = chars.size(); i < n; i++) {
//            mapping[chars[i] - 'a'] = vals[i];
//        }
//
//        int ans = 0, f = 0;
//        for (char c : s) {
//            f = max(f, 0) + mapping[c - 'a'];
//            ans = max(ans, f);
//        }
//        return ans;
//    }
//};

//1749. 任意子数组和的绝对值的最大值

//给你一个整数数组 nums 。一个子数组[numsl, numsl + 1, ..., numsr - 1, numsr] 的 和的绝对值 为 abs(numsl + numsl + 1 + ... + numsr - 1 + numsr) 。
//请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。
//abs(x) 定义如下：
//如果 x 是负整数，那么 abs(x) = -x 。
//如果 x 是非负整数，那么 abs(x) = x 。

//class Solution {
//public:
//    int maxAbsoluteSum(vector<int>& nums) {
//        int ans = 0, f_max = 0, f_min = 0;
//        for (int x : nums) {
//            f_max = max(f_max, 0) + x;
//            f_min = min(f_min, 0) + x;
//            ans = max({ ans, f_max, -f_min });
//        }
//        return ans;
//    }
//};

//1191. K 次串联后最大子数组之和

//给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。
//例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是[1, 2, 1, 2, 1, 2] 。
//返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
//由于 结果可能会很大，需要返回的 109 + 7 的 模 。

//class Solution {
//    // 53. 最大子数组和（repeat 表示重复次数）
//    int maxSubArray(vector<int>& nums, int repeat) {
//        int n = nums.size();
//        int ans = 0, f = 0; // 本题允许子数组为空，ans 可以初始化成 0
//        for (int i = 0; i < n * repeat; i++) {
//            f = max(f, 0) + nums[i % n];
//            ans = max(ans, f);
//        }
//        return ans;
//    }
//
//public:
//    int kConcatenationMaxSum(vector<int>& arr, int k) {
//        if (k == 1) {
//            return maxSubArray(arr, 1);
//        }
//        long long ans = maxSubArray(arr, 2); // arr+arr 的最大子数组和
//        int s = reduce(arr.begin(), arr.end());
//        ans += 1LL * max(s, 0) * (k - 2);
//        return ans % 1'000'000'007;
//    }
//};

//918. 环形子数组的最大和

//给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
//环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
//子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

//class Solution {
//public:
//    int maxSubarraySumCircular(vector<int>& nums) {
//        int max_f = 0; // 计算最大子数组和的 DP 数组（空间优化成一个变量）
//        int max_s = INT_MIN; // 最大子数组和，不能为空
//        int min_f = 0; // 计算最小子数组和的 DP 数组（空间优化成一个变量）
//        int min_s = 0; // 最小子数组和，可以为空（元素和为 0）
//        int sum = 0; // nums 的元素和
//
//        for (int x : nums) {
//            max_f = max(max_f, 0) + x;
//            max_s = max(max_s, max_f);
//            min_f = min(min_f, 0) + x;
//            min_s = min(min_s, min_f);
//            sum += x;
//        }
//
//        return sum == min_s ? max_s : max(max_s, sum - min_s);
//    }
//};

//2321. 拼接数组的最大分数

//给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。
//你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right] 。
//例如，设 nums1 = [1, 2, 3, 4, 5] 和 nums2 = [11, 12, 13, 14, 15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为[1, 12, 13, 4, 5] 而 nums2 会变为[11, 2, 3, 14, 15] 。
//你可以选择执行上述操作 一次 或不执行任何操作。
//数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。
//返回 可能的最大分数 。
//子数组 是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。

//class Solution {
//    int solve(vector<int>& nums1, vector<int>& nums2) {
//        int s1 = 0, max_sum = 0, f = 0;
//        for (int i = 0; i < nums1.size(); i++) {
//            s1 += nums1[i];
//            f = max(f, 0) + nums2[i] - nums1[i];
//            max_sum = max(max_sum, f);
//        }
//        return s1 + max_sum;
//    }
//
//public:
//    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
//        return max(solve(nums1, nums2), solve(nums2, nums1));
//    }
//};

//152. 乘积最大子数组

//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//测试用例的答案是一个 32 - 位 整数。

//class Solution {
//public:
//    int maxProduct(vector<int>& nums) {
//        int ans = INT_MIN;
//        int f_max = 1, f_min = 1;
//        for (int x : nums) {
//            int mx = f_max;
//            f_max = max({ f_max * x, f_min * x, x });
//            f_min = min({ mx * x, f_min * x, x });
//            ans = max(ans, f_max);
//        }
//        return ans;
//    }
//};

//1186. 删除一次得到子数组最大和

//给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
//换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
//注意，删除一个元素后，子数组 不能为空。

//class Solution {
//public:
//    int maximumSum(vector<int>& arr) {
//        int ans = INT_MIN / 2, f0 = ans, f1 = ans;
//        for (int x : arr) {
//            f1 = max(f1 + x, f0);
//            f0 = max(f0, 0) + x;
//            ans = max(ans, max(f0, f1));
//        }
//        return ans;
//    }
//};